package com.edu.study.normal;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Demo {

	public static void main(String[] args) {
		List<Map<String,Object>> dataList = new ArrayList<>();
		setTestData(dataList);
		List<Map<String,Object>> treeNodes = Demo.listTranstoTree(dataList);
		for(Map<String,Object> node : treeNodes) {
			System.out.println(node);
		}
	}

	/**
	 * 设置测试数据
	 * 中国
	 * 	湖南
	 * 		邵阳
	 * 			隆回
	 * 				七江
	 * 				高平
	 * 			洞口
	 * 		岳阳
	 * 	四川
	 * 		成都
	 * 			宜宾
	 * 美国
	 * 	加州
	 * @param dataList
	 */
	public static void setTestData(List<Map<String,Object>> dataList) {
		Map<String,Object> bean = new HashMap<String,Object>();
		bean.put("id", "hunan");
		bean.put("pid", "zg");
		bean.put("text", "湖南");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "chengdu");
		bean.put("pid", "sichuan");
		bean.put("text", "成都");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "shaoyang");
		bean.put("pid", "hunan");
		bean.put("text", "邵阳");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "zg");
		bean.put("pid", "#");
		bean.put("text", "中国");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "yueyang");
		bean.put("pid", "hunan");
		bean.put("text", "岳阳");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "longhui");
		bean.put("pid", "shaoyang");
		bean.put("text", "隆回");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "mg");
		bean.put("pid", "#");
		bean.put("text", "美国");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "dongkou");
		bean.put("pid", "shaoyang");
		bean.put("text", "洞口");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "qijiang");
		bean.put("pid", "longhui");
		bean.put("text", "七江");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "yibin");
		bean.put("pid", "chengdu");
		bean.put("text", "宜宾");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "sichuan");
		bean.put("pid", "zg");
		bean.put("text", "四川");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "jiazhou");
		bean.put("pid", "mg");
		bean.put("text", "加州");
		dataList.add(bean);
		bean = new HashMap<String,Object>();
		bean.put("id", "gaoping");
		bean.put("pid", "longhui");
		bean.put("text", "高平");
		dataList.add(bean);
	}

	/**
	 * 列表转为树 数据格式为 id,pid,text;第一层级节点 pid="#"
	 * @param dataList
	 * @return
	 */
	public static List<Map<String,Object>> listTranstoTree(List<Map<String,Object>> dataList) {
		Iterator<Map<String, Object>> itor = dataList.iterator();
		List<Map<String,Object>> treeNodes = new ArrayList<Map<String, Object>>();
		//获取第一级节点 （pid="#"）
		while(itor.hasNext()) {
			Map<String,Object> node = itor.next();
			if("#".equals(node.get("pid"))) {
				treeNodes.add(node);
				itor.remove();
			}
		}

		Map<String,Boolean> flagMap = new LinkedHashMap<String,Boolean>();
		//设置子节点
		for(Map<String,Object> node:treeNodes) {
			setChildren(node,dataList,flagMap);
		}
		if(dataList.size() > 0) {
			//TODO 还存在未匹配的节点
			System.out.println(dataList);
		}
		return treeNodes;
	}

	/**
	 * 递归设置子节点
	 * @param curNode
	 * @param dataList
	 */
	@SuppressWarnings("unchecked")
	public static void setChildren(Map<String,Object> curNode,List<Map<String,Object>> dataList,Map<String,Boolean> flagMap) {
		Iterator<Map<String, Object>> itor = dataList.iterator();
		String key = curNode.get("id")+"";
		flagMap.putIfAbsent(key, false);//初始化
		Map<String,Object> nextNode;
		List<Map<String,Object>> childList;
		while(itor.hasNext()) {
			//若当前节点存在子节点，再次遍历时，因为dataList已发生改变，遍历器需要重新赋值，否则会触发failfast机制异常。
			if(flagMap.get(key)) {
				itor = dataList.iterator();
				flagMap.put(key, false);//完成一次递归后，就需要重置标识，否则会进入死循环
			}
			//遍历器可能发生变化，需要再次判断，是否有next节点，否则获取next节点时可能报空指针异常
			if(itor.hasNext()) {
				nextNode = itor.next();
				if(curNode.get("id").equals(nextNode.get("pid"))) {
					childList = (List<Map<String, Object>>) (curNode.containsKey("childList") ? curNode.get("childList") : new ArrayList<Map<String, Object>>());
					childList.add(nextNode);
					curNode.put("childList", childList);
					itor.remove();
					flagMap.put(key, true);//设置当前节点存在子节点
					setChildren(nextNode,dataList,flagMap);
				}
			}
		}
	}
}